
class Main {
    public static class BinaryTree {

        static class TreeNode {
            public char val;
            //存储左孩子节点的引用
            public TreeNode left;
            //存储右孩子节点的引用
            public TreeNode right;

            public TreeNode(char val) {
                this.val = val;
            }
        }

        public boolean isSameTree(TreeNode p, TreeNode q) {
            if ((p == null && q != null) || (p != null && q == null)) {
                return false;
            }
            //上述if没有生效 代表什么？要么两个都是空 要么两个都不为空
            if (p == null && q == null) {
                return true;
            }
            //走完第2个if 那么p 和 q 都不为空了
            if (p.val != q.val) {
                return false;
            }
            //上述if执行完毕之后，p != null && q != null && p.val == q.val
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

        /**
         * 时间复杂度O(m*n)
         *
         * @param root    m
         * @param subRoot n
         * @return
         */
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if (root == null) {
                return false;
            }
            if (isSameTree(root, subRoot)) {
                return true;
            }
            if (isSubtree(root.left, subRoot)) {
                return true;
            }
            if (isSubtree(root.right, subRoot)) {
                return true;
            }
            return false;
        }
    }
}